package org.algorithm.wE1.栈.第1周;

import java.util.Stack;

/**
 * @date 2022-04-06 星期三 00:00
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek返回 -1。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-of-stacks-lcci
 */
public class 栈排序 {
    class SortedStack {
        Stack<Integer> stack ;
//        Stack<Integer> preStack;
        public SortedStack() {
            stack = new Stack<>();
//            preStack = new Stack<>();
        }

        public void push(int val) {
            if(!stack.isEmpty()&&val>stack.peek()){
                int pre = stack.pop();
                //递归
                push(val);
                stack.push(pre);
            }else {
                stack.push(val);
            }
        }

        public void pop() {
            if(stack.isEmpty()){
                return;
            }
                stack.pop();
        }

        public int peek() {
            if(stack.isEmpty()){
                return -1;
            }
            return stack.peek();
        }

        public boolean isEmpty() {
            return stack.isEmpty();
        }
    }
}
